
/**
 * 
 * 云短信平台优惠活动
 * 
 * 题目描述

某云短信厂商，为庆祝国庆，推出充值优惠活动。

现在给出客户预算，和优惠售价序列，求最多可获得的短信总条数。

输入描述
第一行客户预算 M

0 ≤ M ≤ 10^6
第二行给出售价表 P1, P2, … Pn，其中 Pi 为充值 i 元获得的短信条数。

1 ≤ n ≤ 100
1 ≤ Pi ≤ 1000
输出描述
最多获得的短信条数

用例
输入	6
10 20 30 40 60
输出	70
说明	分两次充值最优， 1 元、 5 元各充一次。总条数 10 + 60 = 70
输入	15
10 20 30 40 60 60 70 80 90 150         
输出	210
说明	分两次充值最优， 10 元 5 元各充一次，总条数 150 + 60 = 210
 */

import java.util.Arrays;
import java.util.Scanner;

/**
  * 
  题目解析
本题是完全背包问题。

如果大家不是很清楚完全背包的求解，可以看

算法设计 - 01背包问题的状态转移方程优化，以及完全背包问题_伏城之外的博客-CSDN博客

本题中：

客户预算 M 相当于背包的承重，
出售价表：
i 元相当于物品的重量，
Pi 短信条数相当于物品的价值

  */
public class 云短信平台优惠活动 {
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
 
        int m = Integer.parseInt(sc.nextLine());
        int[] p = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
 
        int[] dp = new int[m + 1];
 
        for (int i = 0; i < p.length; i++) {
            // p[0]条短信花费1元，p[i]条短信花费i+1元
            for (int j = i + 1; j <= m; j++) {
                dp[j] = Math.max(dp[j], dp[j - i - 1] + p[i]);
            }
        }
 
        System.out.println(dp[m]);

    }
}
